package com.wujunshen.algorithm.leetcode.dynamic.programming;

/**
 * 根据最大子数组和的思路，我们可以假设 dp[i] 代表处理到 nums[i] 的乘积最大子数组和
 * 易得:
 * <p>
 * dp[i] = max(dp[i-1]*nums[i] , nums[i])
 * <p>
 * 但仔细想想，这个递推公式其实是有问题的，或者说我们忽略了一种情况，故它不符合动态规划的最优子结构要求
 * <p>
 * 我们来分析一下 :
 * <p>
 * 上述公式的含义是: 处理第 i 个位置时乘积最大子数组的值等于第 i-1 个位置的乘积最大子数组的值乘以当前位置的值 或 直接等于当前位置的值。取二者值较大的一方
 * <p>
 * 但是这忽略了一种情况 : 累乘不像累加，每一次的变化仅与当前位置的值有关，累乘有负负得正，即当前的最小值可能在下一次累乘时变为最大值，故正确（或完整）的递推公式还应该添加上该条件 ：
 * 第 i-1 个位置乘积的最小子数组的值 乘以当前位置的值。并比较这三者取值最大的一个
 * <p>
 * 故递推公式实际上为 :
 * <p>
 * dp[i] = max(dp[i-1] * nums[i] , min[i-1] * nums[i] , nums[i])
 * <p>
 * 其中，min[i] 代表处理第 i 个位置时乘积最小子数组的值
 * <p>
 * 上述递推公式中添加了 min[i] ， 不过它的分析与 dp[i] 相同，易得 :
 * min[i] = min(dp[i-1] * nums[i] , min[i-1] * nums[i] , nums[i])
 * <p>
 * 最后，为了对称美观，我们将 dp[i] 写成 max[i] 可得:
 * <p>
 * max[i] = max(max[i-1] * nums[i] , min[i-1] * nums[i] , nums[i]);
 * min[i] = min(max[i-1] * nums[i] , min[i-1] * nums[i] , nums[i]);
 *
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/8/6 17:20<br>
 */
public class 乘积最大子数组 {
    public int maxProduct(int[] nums) {
        int max;
        int min;
        int ans;
        ans = max = min = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int n = nums[i];
            int max1 = Math.max(n , Math.max(n*max , n*min));
            int min1 = Math.min(n , Math.min(n*max , n*min));
            max = max1;
            min = min1;
            ans = Math.max(ans,max);
        }

        return ans;
    }
}
